/*
题目：路径总和Ⅱ
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。
https://leetcode.cn/problems/path-sum-ii
 */
public class PathSumⅡ {
    //广度优先搜索
    List<List<Integer>> list = new ArrayList<> ();
    Map<TreeNode, TreeNode> map = new HashMap<> ();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return list;
        Queue<TreeNode> nodeQueue = new LinkedList<> ();
        Queue<Integer> valQueue = new LinkedList<> ();
        nodeQueue.offer(root);
        valQueue.offer(0); //表示的是到该节点的路径总和

        while (!nodeQueue.isEmpty()) {
            TreeNode curNode = nodeQueue.poll();
            int curVal = valQueue.poll();

            if (curNode.left == null && curNode.right == null) {  //如果是叶子节点
                //当我们走到叶子节点才会发现能不能形成目标路径，所以map的映射，也需要反向映射
                if (curVal + curNode.val == targetSum) {
                    getPath(curNode);
                }
            } else {
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                    valQueue.offer(curVal + curNode.val);
                    map.put(curNode.left, curNode);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                    valQueue.offer(curVal + curNode.val);
                    map.put(curNode.right, curNode);
                }
            }
        }
        return list;
    }

    private void getPath(TreeNode root) {
        List<Integer> path = new ArrayList<> ();
        while (root != null) {
            path.add(root.val);
            root = map.get(root);
        }
        Collections.reverse(path);
        list.add(path);
    }
}
